//== SAGITTARIUS ============================================================================

//== FILEDOC =========================================================================

/** @file lAST.h
  * @brief Abstract syntax tree for the @ref LexerCmdLang "Lexer Command Language"
  */

//== BEGINNING OF CODE ===============================================================

#ifndef __SAGUTTARUIS__LAST__H_
#define __SAGUTTARUIS__LAST__H_

//== INCLUDES ========================================================================

#include "sagittarius/core/SagittariusCore.h"
#include "sagittarius/re/reCS.h"
#include "sagittarius/re/reDC.h"

#define CONST_RECH_AMP       0x26  /*'&'*/
#define CONST_RECH_LPAREN    0x28  /*'('*/
#define CONST_RECH_RPAREN    0x29  /*')'*/
#define CONST_RECH_STAR      0x2A  /*'*'*/
#define CONST_RECH_CARROT    0x5E  /*'^'*/
#define CONST_RECH_VBAR      0x7C  /*'|'*/
#define CONST_RECH_LBRAK     0x5B  /*'['*/
#define CONST_RECH_RBRAK     0x5D  /*']'*/
#define CONST_RECH_BSLASH    0x5C  /*'\'*/
#define CONST_RECH_DASH      0x2D  /*'-'*/
#define CONST_RECH_SPACE     0x20  /*' '*/
#define CONST_RECH_NEWLINE   '\n' //Sick of this hex
#define CONST_RECH_NULLCHR   '\0'
#define CONST_RECH_PLUS      '+'
#define CONST_RECH_QUES      '?'
/// No special meaning in ordinary REs but used by @ref lex_parseID for the @ref LexerCmdLang "Lexer Command Language"
#define CONST_RECH_EQ        '='
/// Used as a comment indicator
#define CONST_RECH_POUND     '#'

//white space
#define CONST_RECH_BLANK     ' '
#define CONST_RECH_TAB       '\t'
#define CONST_RECH_LF        '\n'
#define CONST_RECH_CR        '\r'

#define CONST_RECH_NULL      '\0'

#ifdef __cplusplus
extern "C" {
#endif

/**
 * @brief Types of AST nodes in the @ref LexerCmdLang "Lexer Command Language"
 */
typedef enum {
    //Assignment node
    //AST_NODE_TYPE_ASSN,
    //Identifier node
    //AST_NODE_TYPE_ID,
    //RE types
    ///Primitive node
    AST_NODE_TYPE_REPRIMITIVE,
    //AST_NODE_TYPE_BINOP,
    ///Concatenation node
    AST_NODE_TYPE_RECONCAT,
    ///Union node
    AST_NODE_TYPE_REUNION,//AST_NODE_TYPE_ALTERNATIVE
    ///Intersection node
    AST_NODE_TYPE_REINTERSECTION
} lAST_NodeType;

/**
 * @brief Expression AST node
 */
typedef struct __lASTNode {
    /// @brief The type of node
    lAST_NodeType type;
    
    /// @brief The character set if the node is of type @ref lAST_NodeType "AST_NODE_TYPE_REPRIMITIVE"
    RE_CharSet* cs;
    
    /// @brief The derivative classes of this node; used in DFA construction - See @ref lex_computeDC
    RE_DerivClass* d;
    
    /// @brief The first child (or NULL if there is no first child)
    struct __lASTNode* n1;
    /// @brief The second child (or NULL if there is no second child)
    struct __lASTNode* n2;
    
    //special properties
    /**
     * @brief True if node is negated
     * @details That is, the node actually represents the complement of its expression
     */
    //TODO: specify precedence of inv vs. closed
    int inv;
    /// @brief True if node is closed under Kleene closure
    int closed;
    /// @brief Nullable: a function of a regular exp
    int nullable;
    
    /// @brief Generic data field
    void* p;
} lASTNode;

//called by constructors to initialize
/**
 * @brief Basic AST node constructor
 * @details This basic @ref lASTNode constructor allocates space and sets
 * parameters to default values. These defaults are acceptable for use with
 * the wide range of specialized constructors listed below. Uses @ref LX_ALLOC 
 * to allow basic/pool allocation
 */
lASTNode* lAST_createNode();

/**
 * @brief Basic AST node destructor
 * @param n[in,out] The node to be destroyed (children will be destroyed)
 * @details While it technically isn't necessary to call this
 * function in pool allocator mode, it does no harm as @ref LX_FREE
 * simply wraps to a no-op. In the future this function may be 
 * replaced with a macro for potential slight speed gains.
 */
void lAST_destroy_node(lASTNode* n);

/**
 * @brief Shallow destructor
 * @param[in,out] n The node to be destroyed (children will be @a preserved)
 * @details Unlike @ref lAST_destroy_node, this function does not
 * destroy the descendants of @a n. It is used by @ref lAST_canonicalize
 * in pool mode when performing transformations that reduce certain 
 * constructs to primitive nodes. @b SUGGESTION: Doesn't appear to 
 * be doing anything; remove?
 */
void lAST_destroyShallow(lASTNode* n);

/**
 * @brief Deep copy constructor
 * @param[in] n The node to be copied
 * @details Performs a deep copy on @a n, including all descendents
 * and properties. There is no way to copy the data field n->p yet.
 */
lASTNode* lAST_deepCopy(const lASTNode* n);

/**
 * @brief Shallow copy
 * @param[in] n The node to be copied
 * @details Copies everything but child nodes. The child pointers
 * n1 and n2 of the result will be set to n->n1 and n->n2 respectively.
 * Data cannot be copied.
 */
lASTNode* lAST_shallowCopy(const lASTNode* n);

//Special

/**
 * @brief Computes the derivative classes for this node
 * @param[in] n The input node
 * @details The derivative classes for this node will be computed
 * "bottom-up," i.e. computation will start at the most distal
 * nodes. If a derivative class has already been computed for a
 * particular node, as signaled by the fact that n->d is non-NULL,
 * the routine will not attempt to reevaluate the derivative classes
 * for that node
 */
void lex_computeDC(lASTNode* n);

/**
 * @brief Canonicalizes the given node
 * @param[in,out] n The node to canonicalize
 * @details AST nodes are required to maintain certain properties
 * in order to be considered "canonical." The notion of a canonical
 * form allows the DFA construction engine to evaluate whether two
 * REs (represented respectively by two @ref lASTNode "lASTNodes")
 * are equivalent, in terms of the limited version of equality used
 * by the algorithm. 
 * See @ref CanonicalASTs "Canonical Representation of AST nodes"
 */
void lAST_canonicalize(lASTNode** _n);

//Single node stats
/**
 * @brief Is @a n the empty string?
 * @returns 1 if n is a primitive corresponding to the empty string, 0 otherwise
 * @param[in] n AST node
 */
int lex_isEmptyString(lASTNode* n);
/**
 * @brief Does @a n represent null language?
 * @returns 1 if n is a primitive corresponding to the null language, 0 otherwise
 * @param[in] n AST node
 */
int lex_isNull(lASTNode* n);

//Multi-node stats

#define LEX_COMPARE_LT 1
#define LEX_COMPARE_EQ 2
#define LEX_COMPARE_GT 3
/**
 * @returns LEX_COMPARE_LT if @a r < @a s, LEX_COMPARE_EQ if @a r == @a s, LEX_COMPARE_GT if @a r > @a s
 * @param[in] r AST node
 * @param[in] s AST node
 * @brief Compares two AST nodes using an order relation on REs
 * @details The order relation sorts REs based on the type of operation
 * they represent (union, intersection, Kleene closure, etc.), and the primitives
 * attached to the operation. In general, the specifics of the order relation
 * cannot be relied on across revisions. The essential requirement is that
 * REs be well ordered, otherwise it is not possible to define a canonical
 * form. See @ref CanonicalASTs "Canonical Representation of AST nodes"
 */
int lex_compare(const lASTNode* r, const lASTNode* s);

//Constructors

/**
 * @brief Constructs a primitive AST node for the given single symbol
 * @param[in] c The given symbol
 */
lASTNode* lex_constructSymbol(LXConstAlphaType c);

/**
 * @brief Constructs a primitive AST node for the given single symbol
 * @param[in] c The given symbol
 * @details This method is identical to @ref lex_constructSymbol when
 * compiled without bignum support. Otherwise, it constructs a node
 * based on a fixed symbol (as opposed to a bignum)
 */
lASTNode* lex_constructFixed(LXFixedType c);

/**
 * @brief Constructs a primitive AST node representing the empty str
 * @details Equivalent to @ref lex_constructFixed(@ref CONST_RE_EMPTY_STR)
 */
lASTNode* lex_constructEmptyStr();

/**
 * @brief Constructs a primitive AST node representing the empty str
 * @details Equivalent to @ref lex_constructFixed(@ref CONST_RE_NULL)
 */
lASTNode* lex_constructNull();

/**
 * @brief Union of two expressions
 * @details Constructs a union AST node (@ref AST_NODE_TYPE_REUNION) with
 * @a r and @a s as its operands.
 */
lASTNode* lex_constructNodeUnion(lASTNode* r, lASTNode* s);

/**
 * @brief Union of two expressions
 * @details Constructs a concatenation AST node (@ref AST_NODE_TYPE_RECONCAT) 
 * with @a r and @a s as its operands.
 */
lASTNode* lex_constructNodeConcat(lASTNode* r, lASTNode* s);

/**
 * @brief Union of two expressions
 * @details Constructs a intersection AST node (@ref AST_NODE_TYPE_REINTERSECTION) 
 * with @a r and @a s as its operands.
 */
lASTNode* lex_constructNodeInt(lASTNode* r, lASTNode* s);

//-- Node diagnostics --
/**
 * @brief Dumps info about the node to stdout
 * @param[in] n The node
 * @param n_indent The indentation level to start at
 * @details This will also print any child nodes at a higher indentation
 * level.
 */
void lex_writeOut(int fd, const lASTNode* n, int n_indent);

/**
 * @brief Just prints the type of node
 * @param[in] n The node
 */
void lex_printNodeType(int fd, const lAST_NodeType type);

#ifdef __cplusplus
}//extern "C"
#endif

/**
 * @page CanonicalASTs
 * @brief Canonical Representation of AST nodes
 * @details <b>Describes the notion of RE similarity based on structural equivalence</b><br>
 * See: @ref OwensPaper "Owens et al."
 */

#endif
